# !/usr/bin/env python
# -*- coding: utf-8 -*-
from arr_util import random_scale_arr


# 桶排序
# 基本思想: 桶排序的思想就是把待排序的数尽量均匀地放到各个桶中，再对各个桶进行局部的排序，最后再按序将各个桶中的数输出，即可得到排好序的数。
# 1.首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中，那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值mx和最小值mn；
# 根据mx和mn确定每个桶所装的数据的范围 size，有
# size = (mx - mn) / n + 1，n为数据的个数，需要保证至少有一个桶，故而需要加个1；
# 求得了size即知道了每个桶所装数据的范围，还需要计算出所需的桶的个数cnt，有
# cnt = (mx - mn) / size + 1，需要保证每个桶至少要能装1个数，故而需要加个1；
# 2.求得了size和cnt后，即可知第一个桶装的数据范围为 [mn, mn + size)，第二个桶为 [mn + size, mn + 2 * size)，…，以此类推
# 因此步骤2中需要再扫描一遍数组，将待排序的各个数放进对应的桶中。
# 3.对各个桶中的数据进行排序，可以使用其他的排序算法排序，例如快速排序；也可以递归使用桶排序进行排序；
# 4.将各个桶中排好序的数据依次输出，最后得到的数据即为最终有序。

# 时间复杂度: 最好O(n + k),最坏O(n^2),平均(n + k)
# 空间复杂度: 最好0(已经排好序),最坏O(n)(逆序),平均O(1)
# 稳定性: 稳定
def bucket_sort(num_arr):
    return bucket_self_sort(num_arr, 5, None)


# bucket_size 桶大小
def bucket_self_sort(num_arr, bucket_size=5, sort_func=None):
    min_num = min(num_arr)
    max_num = max(num_arr)
    # 桶内元素数量
    bucket_count = (max_num - min_num) // bucket_size + 1
    # 定义桶数组 buckets
    buckets = [[] for _ in range(bucket_count)]
    # 遍历原始数组元素，将每个元素装入对应区间的桶中
    for num in num_arr:
        buckets[(num - min_num) // bucket_size].append(num)

    # 对每个桶内的元素单独排序，并合并到 res 数组中
    res_arr = []
    for bucket in buckets:
        if sort_func is None:
            bucket.sort()
        else:
            sort_func(bucket)
        res_arr.extend(bucket)
    return res_arr


if __name__ == '__main__':
    arr = [1, 2, 5, 7, 6, 5, 4]
    res = bucket_sort(arr)
    print(res)
    arr2 = random_scale_arr(20, 500)
    res2 = bucket_sort(arr2)
    print(res2)
